import numpy as np
import math
def computeMatrix(A, B, n):
    '''
    Suppose the matrix is square matrix
    :param A:square matrix
    :param B:square matrix
    :param n:size of matrix
    :return:matrix time
    '''
    if n == 1:
        return np.dot(A, B)
    else:
        C = np.zeros((n,n),dtype=int)
        half_n = n//2
        listSubA = divideMatrix(A,half_n,n)
        listSubB = divideMatrix(B,half_n,n)
        P1 = computeMatrix(listSubA[0], listSubB[1], half_n) - computeMatrix(listSubA[0], listSubB[3], half_n)
        P2 = computeMatrix(listSubA[0], listSubB[3], half_n) + computeMatrix(listSubA[1], listSubB[3], half_n)
        P3 = computeMatrix(listSubA[2], listSubB[0], half_n) + computeMatrix(listSubA[3], listSubB[0], half_n)
        P4 = computeMatrix(listSubA[3], listSubB[2], half_n) - computeMatrix(listSubA[3], listSubB[0], half_n)
        P5 = computeMatrix(listSubA[0], listSubB[0], half_n) + computeMatrix(listSubA[0], listSubB[3], half_n) + \
             computeMatrix(listSubA[3], listSubB[0], half_n) + computeMatrix(listSubA[3], listSubB[3], half_n)
        P6 = computeMatrix(listSubA[1], listSubB[2], half_n) + computeMatrix(listSubA[1], listSubB[3], half_n) - \
             computeMatrix(listSubA[3], listSubB[2], half_n) - computeMatrix(listSubA[3], listSubB[3], half_n)
        P7 = computeMatrix(listSubA[0], listSubB[0], half_n) + computeMatrix(listSubA[0], listSubB[1], half_n) - \
             computeMatrix(listSubA[2], listSubB[0], half_n) - computeMatrix(listSubA[2], listSubB[1], half_n)
        C[0:half_n, 0:half_n] = P5 + P4 - P2 + P6
        C[0:half_n, half_n:n] = P1 + P2
        C[half_n:n, 0:half_n] = P3 + P4
        C[half_n:n, half_n:n] = P5 + P1 - P3 -P7
        return C
def divideMatrix(A,half_n,n):
    '''

    :param A:
    :param half_n:
    :param n:
    :return: four sub matrix
    '''
    a11 = A[0:half_n, 0:half_n]
    a21 = A[half_n:n, 0:half_n]
    a12 = A[0:half_n, half_n:n]
    a22 = A[half_n:n, half_n:n]
    return (a11, a12, a21, a22)
if __name__ == '__main__':
    A = np.array([[1,3],[7,5]])
    B = np.array([[6,8],[4,2]])
    print(computeMatrix(A,B,2))
    print(np.dot(A,B))
